sortlistmodel: Fix a crash

dropdown: Fix popup sizing

Setting a width request is not quite enough, since
gtk_widget_set_size_request() only queues a resize
when the widget is visible. Explicitly force one
here. Without this, the popup sometimes shows up
too small.

Merge branch 'fix-gdk-array-msvc' into 'master'

gdk/gdkarrayimpl.c: Fix build on Visual Studio

See merge request GNOME/gtk!2279

gdk/gdkarrayimpl.c: Fix build on Visual Studio

It seems like initializing something to an empty array using `{}` is a GCCism,
so just stuff a 0 within the braces to accomplish the same thing.

Merge branch 'matthiasc/for-master' into 'master'

filechooser: Remove a leftover signal emission

Closes #2942

See merge request GNOME/gtk!2276

docs: Work around escaping bugs

This is truly a russian doll of documentation formats:
a string containing <> inside an xml fragment in an |[ ]|
gtk-doc example in markdown in a doc comment.

Sadly, something gets escaping wrong, so the <> end up
literally in the docbook and mess up the last step of
our document formatting, even after turning them into
entities.

Work around this with an extra level of entities that
really shouldn't be necessary.

docs: Pass --standalone to pandoc

This flag causes pandoc to emit a proper doctype
declaration and, crucially, namespace declarations
for the xlink namespace that it insists on using
for href attributes. Without this, putting external
links in md documents doesn't survive the journey
through xml.

docs: Improve shortcut trigger docs

Point out the need to escape <> in xml.

docs: Explain the shortcutcontroller example a bit

Add a reference to the the syntax for shortcut actions
in builder files.

filechooser: Remove a leftover signal emission

Commit 0145809a94667c75ed4a4 replace the response-requested
signal with an action, but didn't actually remove the emission
of that no-longer-existing signal.

Fixes: #2942

Merge branch 'wip/otte/for-master' into 'master'

Wip/otte/for master

See merge request GNOME/gtk!2277

searchenginemodel: Remove unused code

searchengine: Remove unused set_recursive() call

Update Romanian translation

Update Romanian translation

Merge branch 'matthiasc/for-master' into 'master'

Matthiasc/for master

See merge request GNOME/gtk!2275

NEWS: Updates

migration guide: Add some tables

Add a table mapping event signals to their event controller
replacements, and a table mapping former GtkContainer
subclasses to their gtk_container_add replacement.

Merge branch 'wip/otte/for-master' into 'master'

timsort: Actually 0-terminate the array in get_runs()

See merge request GNOME/gtk!2274

timsort: Actually 0-terminate the array in get_runs()

This could cause SEGVs when changing the sort during an ongoing sort
operation.

Update Ukrainian translation

Update Ukrainian translation

Merge branch 'wip/otte/sortlistmodel2' into 'master'

Massively refactor and improve sortlistmodel

See merge request GNOME/gtk!2273

Update POTFILES.in

gtk-demo: Add a progress bar when the colors demo resorts

sortlistmodel: Add progress estimation

timsort: Add progress estimation

sortlistmodel: Make key generation part of the step function

SSave the missing keys as a bitset and iterate over that bitset in the
step function.

Solves the problem with a large UI block at the beginning of a sort
operation when all the keys were generated, in particular when key
generation was slow.

Benchmarks for maximum time taken by a single main loop callback:

     initial sort with complex GFileInfo keys
                       old      new
      32,000 items   137ms      3ms
     128,000 items   520ms     31ms

     initial sort with string keys
                       old      new
      32,000 items   187ms      1ms
     128,000 items   804ms      3ms

gtk-demo: Make colors demo do incremental sorting

sortlistmodel: Properly compute runs

When updating a (partially) sorted model, take the known runs for the
existing sort and apply them to the new sort. That way, we don't have to
check the whole model again.

Benchmarks:

      appending half the items to a model of strings
                        old      new
      512,000 items   437ms    389ms
    1,024,000 items  1006ms    914ms

      appending 10% of the items to a model of strings
                        old      new
      512,000 items   206ms    132ms
    1,024,000 items   438ms    301ms

      appending 1 item to a model of strings
                        old      new
       64,000 items   1.8ms   0.00ms
      512,000 items     ---   0.01ms

sortlistmodel: Make sort stable again

Previously, the sort was not stable when items were added/removed while
sorting or the sort algorithm was changed.

Now the sort looks at the item position (via the key's location in the
keys array) to make sure each comparison stays stable with respect to
this position.

multisorter: Implement GtkSortKeys

treelistrowsorter: Implement GtkSortKeys

numericsorter: Implement GtkSortKeys

stringsorter: Implement GtkSortKeys

sortkeys: Add an equal sort keys

Compares every element as equal.
This is useful when sorters are in an invalid configuration.

sortlistmodel: Use GtkSortKeys

This massively speeds up sorting with expensive sort functions that it's
the most worthwhile optimization of this whole branch.
It's slower for simple sort functions though.

It's also quite a lot slower when the model doesn't support sort keys
(like GtkCustomSorter), but all the other sorters do support keys.

Of course, this depends on the number of items in the model - the number
of comparisons scales O(N * log N) while the overhead for key handling
scales O(N).
So as the log N part grows, generating keys gets more and more
beneficial.

Benchmarks:

       initial sort of a GFileInfo model with display-name keys
                       items     keys
         8,000 items   715ms     50ms
        64,000 items     ---    554ms

       initial sort of a GFileInfo model with complex keys
                       items     keys
        64,000 items   340ms    295ms
       128,000 items   641ms    605ms

       removing half a GFileInfo model with display-name keys
       (no comparisons, just key freeing overhead of a complex sorter)
                       items     keys
       512,000 items    14ms     21ms
     2,048,000 items    40ms     62ms

       removing half a GFileInfo model with complex keys
       (no comparisons, just key freeing overhead of a complex sorter)
                       items     keys
       512,000 items    90ms    237ms
     2,048,000 items   247ms    601ms

sorter: Introduce GtkSortKeys

GtkSortKeys is an immutable struct that can be used to manage "sort
keys" for items.

Sort keys are memory that is created specifically for sorting. Because
sorting involves lots of comparisons, it's a good idea to prepare the
data relevant for sorting in advance and sort on that data.

In measurements with a PropertyExpression on a string sorter, it's about
??? faster

sortlistmodel: Split the SortItem into 2 arrays

Instead of one item keeping the item + its position and sorting that
list, keep the items in 1 array and put the positions into a 2nd array.

This is generally slower while sorting, but allows multiple improvements:

1. We can replace items with keys
   This allows avoiding multiple slow lookups when using complex
   comparisons

2. We can keep multiple position arrays
   This allows doing a sorting in the background without actually
   emitting items-changed() until the array is completely sorted.

3. The main list tracks the items in the original model
   So only a single memmove() is necessary there, while the old version
   had to upgrade the position in every item.
Benchmarks:

        sorting a model of simple strings
                          old      new
        256,000 items   256ms    268ms
        512,000 items   569ms    638ms

        sorting a model of file trees, directories first, by size
                          old      new
         64,000 items   350ms    364ms
        128,000 items   667ms    691ms

        removing half the model
                          old      new
        512,000 items    24ms     15ms
      1,024,000 items    49ms     25ms

sortlistmodel: Add an incremental property

Also refactor a large part of the sortmodel to make this convenient.

A large amount of time has been spent on getting items-changed regions
minimized.

testsuite: Add exhaustive sortlistmodel test

This is basically a copy/paste from the filterlistmodel test, but
adapted for sorting.

sortlistmodel: Make the sort callback useful

1. Run step() for a while to avoid very short steps
   This way, we batch items-changed() emissions.

2. Track the change region accurately
   This way, we can avoid invalidating the whole list if our step just
   touched a small part of a huge list.
   As this is a merge sort, this is a common occurence when we're buys
   merging chunks: The rest of the model outside those chunks isn't
   changed.

Note that the tracking is accurate: It determines the minimum change
region in the model.

This will be important, because the testsuite is going to test this.

timsort: Add change tracking to gtk_tim_sort_step()

timsort: Add gtk_tim_sort_set_max_merge_size()

Makes the SOrtListModel responsive when incrementally sorting.

By making it configurable we can avoid losting performance in the
non-incremental case.

timsort: Make sure merges don't take too long

Limit the size of the merged areas and thereby chunk larger merges into
smaller ones.

sortlistmodel: Make sorting incremental

This is just an experiment so far to see how long it takes to sort.

timsort: Add gtk_tim_sort_set_runs()

... and use it in the SortListModel

Setting runs allows declaring already sorted regions so the sort does
not attempt to sort them again.

This massively speeds up partial inserts where we can reuse the sorted
model as a run and only resort the newly inserted parts.

Benchmarks:

    appending half the model
                    qsort  timsort
    128,000 items    94ms     69ms
    256,000 items   202ms    143ms
    512,000 items   488ms    328ms

    appending 1 item
                    qsort  timsort
      8,000 items   1.5ms    0.0ms
     16,000 items   3.1ms    0.0ms
              ...
    512,000 items     ---    1.8ms

sortlistmodel: Use timsort

Simply replace the old qsort() call with a timsort() call.

This is ultimately relevant because timsort is a LOT faster in merging
to already sorted lists (think items-chaged adding some items) or
reversing an existing list (think columnview sort order changes).

Benchmarks:

    initially sorting the model
                    qsort  timsort
    128,000 items   124ms    111ms
    256,000 items   264ms    250ms

Add a timsort() implementation

sortlistmodel: Track item positions

The model now tracks the original positions on top of just the items so that
it can remove items in an items-changed emission.

It now takes twice as much memory but removes items much faster.

Benchmarks:

Removing 50% of a model:
                   before    after
   250,000 items    135ms     10ms
   500,000 items    300ms     25ms

Removing 1 item:
     4,000 items    2.2ms      0ms
     8,000 items    4.6ms      0ms
   500,000 items      ---   0.01ms

sortlistmodel: Replace with an array-based model

This is the dumbest possible sortmodel using an array:
Just grab all the items, put them in the array, qsort() the array.

Some benchmarks (setting a new model):

  125,000 items - old: 549ms
                  new: 115ms
  250,000 items - new: 250ms

This performance can not be kept for simple additions and removals
though.

Update Chinese (China) translation

Update Chinese (China) translation

Update Chinese (China) translation

Merge branch 'wip/chergert/quartz4u' into 'master'

Merge GDK macOS branch

See merge request GNOME/gtk!2272

Merge branch 'matthiasc/for-master' into 'master'

gdk: Update gdkkeysyms.h

See merge request GNOME/gtk!2271

macos: prototype new GDK backend for macOS

This is fairly substantial rewrite of the GDK backend for quartz and
renamed to macOS to allow for a greenfield implementation.

Many things have come across from the quartz implementation fairly
intact such as the eventloop integration design and discovery of
event windows from the NSEvent.

However much has been changed to fit in with the new GDK design and
how removal of child GdkWindow have been completely eliminated.
Furthermore, the new GdkPopup allows for regular NSWindow to be used
to provide popovers unlike the previous implementation.

The object design more closely follows the ideal for a GDK backend.

Views have been broken out into subclasses so that we can support
multiple GSK renderer paths such as GL and Cairo (and Metal in the
future). However mixed mode GL and Cairo will not be supported. Currently
only the Cairo renderer has been implemented.

A new frame clock implementation using CVDisplayLink provides more
accurate information about when to draw drawing the next frame. Some
testing will need to be done here to understand the power implications
of this.

This implementation has also gained edge snapping for CSD windows. Some
work was also done to ensure that CSD windows have opaque regions
registered with the display server.

     ** This is still very much a work-in-progress **

Some outstanding work that needs to be done:

 - Finish a GL context for macOS and alternate NSView for GL rendering
   (possibly using speciailized CALayer for OpenGL).
 - Input rework to ensure that we don't loose remapping of keys that was
   dropped from GDK during GTK 4 development.
 - Make sure input methods continue to work.
 - Drag-n-Drop is still very much a work in progress
 - High resolution input scrolling needs various work in GDK to land
   first before we can plumb that to NSEvent.
 - gtk/ has a number of things based on GDK_WINDOWING_QUARTZ that need
   to be updated to use the macOS backend.

But this is good enough to start playing with and breaking things which
is what I'd like to see.

gdk: disable file transfer portal on macOS

build: add ATK fallback subproject wrapper

Very similar to the other fallbacks we use.

build: squash various warnings with Clang

Otherwise we have really chatty builds that make it difficult to catch
new issues when compiling.

build: fix linking support on macOS with Clang

This was preventing any sort of building on macOS, even though the quartz
backend is currently non-functional. Fixing this is a pre-requisite to
getting a new macOS backend compiling.

gdk: Update gdkkeysyms.h

Run the gdkkeysyms-update.pl script to pick up several
new keysyms:
GDK_dead_lowline
GDK_dead_aboveverticalline
GDK_dead_belowverticalline
GDK_dead_longsolidusoverlay
GDK_Keyboard
GDK_WWAN
GDK_RFKill
GDK_AudioPreset

Merge branch 'matthiasc/for-master' into 'master'

inspector: Make picking objects show them

Closes #1876

See merge request GNOME/gtk!2269

inspector: Make picking objects show them

Changing the selection in the object tree is
not a useful action if we are already in the
object details. Most likely, a user who picks
an object wants to inspect its details, so
just always show them.

Fixes: #1876

sortlistmodel: Test that the model is stable

Stability is measured relative to the child model, not relative to the
previous sorter.

testsuite: Fix a leak

Merge branch 'barthalion/asan-runner' into 'master'

ci: Switch ASAN tests to runners tagged so

See merge request GNOME/gtk!2267

Merge branch 'action-muxer-speedup' into 'master'

Action muxer speedup

See merge request GNOME/gtk!1754

ci: Switch ASAN tests to runners tagged so

actionmuxer: Update docs and clean up headers

Update the doc comment at the top to describe the
current  functionality of GtkActionMuxer.

actionmuxer: Use an array for accels

We have a lot of accels across all the muxers, but the vast
majority has just one or two, so an array is going to be
smaller and faster for this.

actionmuxer: Create observed_actions and groups on demand

The vast majority of action muxers don't have observers or
groups, so we can avoid the overhead of carrying all these
empty hash tables.

inspector: Make the actions tab work again

Bring back the actions tab; we don't receive
changes anymore, since GtkActionMuxer lost
the GActionGroup signals for this, and the
action observer machinery has no way to listen
for all changes.

Add gtk_action_muxer_list_actions

This is needed to reinstate the actions support
in the inspector.

actionmuxer: Stop implementing GActionGroup

Instead of implementing the GActionGroup interface
and using its signals for propagating changes up
and down the muxer hierarchy, use the GtkActionObserver
mechanism. This cuts down on the signal emission
overhead.

actionmuxer: Port internal users

Port all internal users of the action muxer
from the GActionGroup interface to the new
action muxer apis.

actionmuxer: Add some more api

We want to drop the GActionGroup interface from
GtkActionMuxer, so add the necessary api directly
to GtkActionMuxer itself.

inspector: Remove action support temporarily

This is using the action muxer as a GActionGroup,
and we want to remove that interface from GtkActionMuxer.

The support will come back later.

Speed up action muxer setup more

Don't emit signals for group insertion/removal
if nobody is listening.

Speed up action muxer setup

We don't need to duplicate all these action names and
emit all these signals if nobody is listening.

Merge branch 'matthiasc/for-master' into 'master'

Matthiasc/for master

See merge request GNOME/gtk!2266

gsk: Remove an unused debug flag

GSK_DEBUG_DIFF was not used anywhere, so remove it.

inspector: Add a few more debug flags

Add check buttons for GTK_DEBUG=constraints and
GTK_DEBUG=layout in the logs page.

Tweak the GTK_DEBUG=help output

I got the layout flag wrong when I added the
improved help output. It is about layout managers,
not about showing layout borders.

Merge branch 'list-model-docs' into 'master'

List model docs

See merge request GNOME/gtk!2182

Merge branch 'matthiasc/for-master' into 'master'

Matthiasc/for master

See merge request GNOME/gtk!2265

windowhandle: Don't use an action muxer needlessly

The api that is meant to be used here is
gtk_widget_activate_action.

NEWS: Updates

Merge branch 'matthiasc/for-master' into 'master'

Matthiasc/for master

See merge request GNOME/gtk!2264

button: Add explicit key bindings for activation

We should not rely on GtkWindow to have global
"activate-default" key bindings that happen to
fall back to activating the focus widget. This is
unreliable, since the bubbling up from the button
to the toplevel may run across other widgets that
may want to use Enter for their own purpose, and
then the button loses out. By adding our own
key bindings, the button gets to handle it before
its ancestors.

This fixes check buttons in the inspector property
list not reacting to Enter despite having focus.

text: Claim clicks when grabbing focus

If we don't, an ancestor (such a GtkListItemWidget)
may interpret the click as "I should grab focus!",
and still our focus away. This was causing hard-to-focus
entries in the property list in the inspector.

inspector: Add focus handling to the property editor

We want to focus the actual control here.

editablelabel: Stop editing on focus-out

This is the expected behavior for the main use case,
treeview-like 'edit one cell at a time'.

fixup editing style class

editablelabel: Document css nodes

Just the usual.

editablelabel: Add a style class while editing

Add the .editing style class to the editable label
while it is editing. The idea is that themes can
show a frame around the entry.

Merge branch 'wip/ricotz/annotations' into 'master'

gtk: Improve g-i annotations for methods of GtkExpression subclasses

See merge request GNOME/gtk!2263

gtk: Improve g-i annotations for methods of GtkExpression subclasses

inspector: Clean up GtkInspectorGeneral

Drop the Private struct.

inspector: Clean up GtkInspectorMiscInfo

Drop the Private struct.